#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *多重背包问题
 * */

// 先遍历物品，在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4, 5};
    vector<int> value = {15, 20, 30, 10};
    int bagWeight = 5;
    vector<int> dp(bagWeight + 1, 0);
    for (int i = 0; i < weight.size(); i++) { // 遍历物品
        //我建议都直接写背包容量就行了 后面if过滤
        for (int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;

}

//第二种方法
void test_CompletePack1() {
    vector<int> weight = {0, 1, 3, 4};
    vector<int> value = {0, 15, 20, 30};
    int bagWeight = 4;                            //背包大小
    int dp[100][100] = {{0}};                    //动态规划表

    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= bagWeight; j++) {
            //相当于每次拿成倍的数量
            for (int k = 0; (j - k * weight[i]) >= 0; ++k) {
                if (j < weight[i])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * weight[i]] + k * value[i]);
            }
        }
    }
    //动态规划表的输出 60

    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            printf("%4d", dp[i][j]);
        }
        cout << "\n";
    }


    cout << dp[4][5] << "---";//10

}


void test_CompletePack3() {
    vector<int> weight = {0, 1, 3, 4, 5};
    vector<int> value = {0, 15, 20, 30, 10};
    int bagWeight = 5;                         //背包大小
    int dp[100][100] = {{0}};                    //动态规划表

    //先物品
    for (int i = 1; i <= 4; i++) {

        //后背包 应该是不这样会出错 01 背包好像都行
        for (int j = 1; j <= bagWeight; j++) {
            //相当于每次拿成倍的数量
            if (j < weight[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

        }
    }
    //动态规划表的输出 60
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            printf("%4d", dp[i][j]);
        }
        cout << "\n";
    }


    cout << dp[4][5] << " test_CompletePack3";//10

}

